package 笔试强训;

public class Test3 {
    //题目  : 笔试强训 day34 第3 题  : 矩阵最长递增路径
    //算法 dfs 记忆化搜索  递归
    public static int n;
    public static int m;
    public static int[] dx = {0,0,1,-1};
    public static int[] dy = {1,-1,0,0};
    //搞一个 同规模数组来标记一下每个点的最长递增路径
    public static int[][] ret = new int[2000][2000];

    public int solve (int[][] matrix) {
        //记忆化搜索  找出每个点的最长递增路径
        n = matrix.length;
        m = matrix[0].length;
        //初始化  ret数组 为-1
        for(int i = 0; i < n; i++) {
            for(int j = 0;j < m; j++) {
                ret[i][j] = -1;
            }
        }
        int count = 1; //记录一下 最大的长度
        for(int i = 0;i < n; i++) {
            for(int j = 0;j < m; j++) {
                //取最大值
                count = Math.max(count,dfs(matrix,i,j));
            }
        }



        return count;
    }

    public static int dfs(int[][] matrix,int i, int j) {

        if(ret[i][j] != -1) {
            return ret[i][j];  //说明已经递归过了记录下来了 直接返回 记录数组的值
        }
        int count1 = 1;  //一开始最小的都是1
        for(int k = 0; k < 4;k++) {
            //上下左右四个方向搜索
            int x = i+dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && matrix[x][y] > matrix[i][j]) {
                //在原有的基础上 +1
                count1 = Math.max(count1,1 + dfs(matrix,x,y));
            }
        }
        ret[i][j] = count1;
        return count1;
    }
}
